---@coding utf8



---@class MinHeap
MinHeap = MinHeap or {}

---@param cmp_fun nil|fun(l, r):boolean
function MinHeap.new(cmp_fun)
    local obj = {}
    setmetatable(obj, {__index = MinHeap})
    obj:_constructor(cmp_fun)
    return obj
end

---@param cmp_fun nil|fun(left, right):boolean
function MinHeap:_constructor(cmp_fun)
    ---@type any[]
    self.heap_data = {}
    self.heap_size = 0
    self.cmp_fun = cmp_fun or _DefaultCmpFun
end

function MinHeap:Size()
    return self.heap_size
end

function MinHeap:Empty()
    return self.heap_size == 0
end

function MinHeap:Clear()
    self.heap_data = {}
    self.heap_size = 0
end

function MinHeap:Peek()
    if self:Empty() then
        return nil
    end
    return self.heap_data[self.heap_size]
end

function MinHeap:Pop()
    if self:Empty() then
        return nil
    end
    local val = self.heap_data[1]
    self.heap_data[1] = self.heap_data[self.heap_size]
    self.heap_data[self.heap_size] = nil
    self.heap_size = self.heap_size - 1
    self:_HeapDown(1)
    return val
end

function MinHeap:Push(val)
    self.heap_data[self.heap_size + 1] = val
    self.heap_size = self.heap_size + 1
    self:_HeapUp(self.heap_size)
end

---@brief 上浮
function MinHeap:_HeapUp(idx)
    local heap_data = self.heap_data
    local heap_size = self.heap_size
    if idx < 1 or idx > heap_size then
        return
    end
    -- 开始上浮扫描: 根节点一定小于子节点
    while idx > 1 do
        local parent_idx = math.floor(idx / 2)
        if self.cmp_fun(heap_data[idx], heap_data[parent_idx]) then
            heap_data[idx], heap_data[parent_idx] = heap_data[parent_idx], heap_data[idx]
            idx = parent_idx
        else
            break
        end
    end
end

---@brief 下沉
function MinHeap:_HeapDown(idx)
    local heap_data = self.heap_data
    local heap_size = self.heap_size
    if idx < 1 or idx > heap_size then
        return
    end
    -- 扫描下沉
    while true do
        local min_idx = idx
        local left_idx = idx * 2 + 1
        local right_idx = idx * 2 + 2
        if left_idx < heap_size and self.cmp_fun(heap_data[left_idx], heap_data[min_idx]) then
            min_idx = left_idx
        end
        if right_idx < heap_size and self.cmp_fun(heap_data[right_idx], heap_data[min_idx]) then
            min_idx = right_idx
        end
        if min_idx ~= idx then
            heap_data[idx], heap_data[min_idx] = heap_data[min_idx], heap_data[idx]
            idx = min_idx
        else
            break
        end
    end
end



function _DefaultCmpFun(left, right)
    return left < right
end


-- --- 测试代码
-- local start_clock, finish_clock, cost_clock = 0, 0, 0
-- ---@type MinHeap
-- local heap = MinHeap.new(nil)
-- local max_size = 1000000
-- start_clock = os.clock()
-- for idx = 1, max_size do
--     heap:Push(math.random(1, 24 * 60 * 60))
-- end
-- cost_clock = os.clock() - start_clock
-- print("push", cost_clock)

-- local heap_size = heap:Size()
-- start_clock = os.clock()
-- while not heap:Empty() do
--     heap:Pop()
-- end
-- cost_clock = os.clock() - start_clock
-- print(string.format("pop,cost_ms=%s,avg_cost_ms=%.3f", cost_clock * 1000, cost_clock * 1000 / heap_size))
